package base.sort;

import base.utils.PrintUtils;

import java.util.Arrays;

/**
 * 插入排序
 * 设计思想  ： 一个记录插入到已经排好序的有序表中
 * 这里进行排序
 *
 * https://www.runoob.com/w3cnote/insertion-sort.html
 */
public class InsertSort implements IArraySort {

    /**
     * 在这里左边的内容是已经有顺序的内容，
      */

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            int tmp = arr[i];                          //记录要插入数据，同时记录i,将i left边的数据进行比较，当需要记录的数据> 比较数据时，则停止记录，否则j--
                                                        //这里的tmp是固定的，在这里左边的内容是已经排序完成的，只需要找到比tmp小的内容就停止
            int j = i;                                // 从已经排序的序列最右边的开始比较，找到比其小的数, 所以j需要是递减

            while (j > 0 && arr[j - 1] >tmp ) {         // 这里让插入数据和已经排序的内容进行对比，如果 tmp <  arr[j-1 ] 则：arr[j-1] 向右移动一个位置
                arr[j] = arr[j - 1];                  //相当于将j-1  向右移动了到了  j  位  ，
                j--;                                //当不能满足循环条件时，则执行  j--;
            }

            // 存在比其小的数，插入到对应j的位置   ，j进行了--  ， 说明  存在 比 arr[i]  大的数
            if (j != i)  arr[j] = tmp;           //同时 j 因为记录下了对应坐标的位置，

        }
        return arr;
    }



    public static void insertSort(int[] arr) {
        int arrSize = arr.length;

        for (int i = 1 ;i < arrSize ; i++){

            int tmp = i;

            while (tmp > 0 && (arr[tmp - 1] > arr[tmp])) {
                int var = arr[tmp];
                arr[tmp] = arr[tmp - 1];
                arr[tmp - 1] = var;
                tmp--;
            }
        }


    }

    public static void sortArray3(int[] sourceArray) {
        int len = sourceArray.length;
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, len);
        for (int i = 1; i < len; i++) {
            int tmp = arr[i];
            int j = i;

            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            if (j != i) arr[j] = tmp;
        }
    }

    public static void insertSortDemo01(int[] arr){

        int arrSize = arr.length;

        for (int i = 1 ; i <arrSize ; i++){
            int j = i;
            int temp = arr[i];

            while (j > 0 && arr[j - 1] > temp ){
                arr[j] = arr[j -1];
                j--;
            }

            if (j != i ){
                arr[j] = temp;
            }

        }

    }





    //方式2
    public static void sort02(int[] arr){
        int len = arr.length;
        int[] list = Arrays.copyOf(arr, len);

        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0 && list[j] < list[j - 1]; j--) {
                //当  j-1   >  j  时进行交换  ，这里将需要插入的数值作为了数组的一部分，然后进行了冒泡
                int sub = list[j];
                list[j] = list[j - 1];
                list[j - 1] = sub;
            }
        }
    }





}
